1. Field of the Invention
The invention is a method and an apparatus for identifying a least recently used (LRU) item of a group or set of items, such as the least recently used data entry associated with a memory cache.
2. Background
In a computer system, data is stored in a memory, such as a hard disk, a random access memory (RAM), or other memory. These memories are capable of storing large amounts of data, but they may be relatively slow or difficult to access. A small, fast memory known as a "cache memory" is used to store a subset of data stored in larger memory. The computer looks first in the cache to see if desired data is available, and if so, obtains it quickly from the cache memory. This is known as a cache "hit". If the desired data is not found in the cache, a cache "miss", the computer retrieves the data from a larger memory and then stores it in the cache for future use. There is a problem in the prior art of determining where in the cache to store the most recently retrieved data.
In many situations, the newly retrieved data replaces the least recently used (LRU) data already found in the cache. This scheme is based on the theory that the least recently used data is less likely to be accessed anytime soon than the more recently selected data.
There are several prior art methods for determining which data associated with the cache is the least recently used. Generally, the cache memory cache can be thought of as a plurality of lines of memory, where each line can store some retrieved data from larger memory. Each line of cache memory is an address at which data can be stored. In one prior art method, a time stamp is associated with each cache address at the time data is placed into the address location. This arrangement is illustrated in FIG. 1. In this example, the memory cache has sixty-four (64) entries or addresses each having associated "time" data "TS" from a time stamp. As an example, the memory cache may comprise a 64.times.32 memory and the time stamp may comprise a 12 bit stamp indicating month, day, year, hour, minute and second. The least recently used item associated with the cache may be identified from the address or entry having the "oldest" time as indicated by the time stamps.
This method has several disadvantages. One problem is that the time stamp requires a large number of bits to facilitate a time stamp which has sufficient precision to identify the relative age of items. For example, the twelve (12) bit time stamp described above only permits the time stamp to indicate time to the nearest second. In such a case, many entries may be time stamped with the same time, preventing them from being distinguished as the least recently used.
Another problem is that substantial effort is required to identify the least recently used item. In the case of the above-referenced 64.times.32 memory, if one uses a 4-way search (that is, a search in which four comparisons can be made per cycle) it takes 64 cycles to read through all of the entries and determine the oldest time stamp, and thus the least recently used entry. Even if the memory cache is divided into two 32.times.32 memories, it takes thirty-three (33) cycles to determine the oldest time stamp.
In another method, a global counter is associated with the memory cache and counts each access to the cache. This arrangement is generally illustrated in FIGS. 2(a-b). Each address or entry of the cache is provided with a count value equal to the count value (C0-C63) of the global counter at the time the entry is accessed. In the arrangement illustrated in FIG. 2(a), the memory has sixty-four (64) addresses or entries, where each entry has been accessed in order and the global count values have been assigned in order.
The least recently used entry is defined as that entry having the lowest associated count value. By searching for the lowest count value in the cache, the least recently used item is supposed to be identifiable.
This arrangement has the significant drawback that the counter will eventually "roll-over" or reset. For example, if the global counter is a six (6) bit counter permitting sixty-four (64) count values from zero (0) to sixty-three (63), the counter will roll over to zero (0) at the next cache access after sixty-three (63). When the counter rolls over, the new entry is assigned the count value of zero (0). This arrangement is illustrated in FIGS. 2(a) and 2(b).
It is noted that the cache is commonly accessed without replacing the least recently used item. In the case illustrated in FIG. 2(b), when the global counter has a count value of sixty-three (63), address or entry E3 is accessed. The global counter resets to zero (0) and assigns count value zero (0) to entry E3.
If the next access of the cache is for the purpose of replacing the least recently used item with an item just retrieved remotely, it is not possible to correctly identify the least recently used item. In the example illustrated in FIG. 2(b), entries E1 and E3 both have assigned count values of zero (0). This is a problem not only because there are two entries with the same count value, but also because the item associated with one entry is actually the oldest and the item associated with the other entry is the newest. This problem results from the "rollover" problem associated with the global counter. With two possible entries being the least recently used entry, the chance of identifying the LRU item correctly is 50%. If a more recently used item is overwritten, and then that same item is requested in a subsequent memory access, the data will not be there, resulting in a cache miss. Cache efficiency is reduced as the number of cache misses increases.
Another problem with this method is that, as with the time stamp system, many cycles of comparisons are required to find the lowest count value to identify the entry or address containing the least recently used item. The large number of comparisons limits system performance.
A method and apparatus for identifying the least recently used item of a group of items which overcomes these problems is desired.